package com.gxc.array;

import java.util.HashMap;

/**
 * 3117. 划分数组得到最小的值之和

 * 给你两个数组 nums 和 andValues，长度分别为 n 和 m。
 *
 * 数组的 值 等于该数组的 最后一个 元素。
 *
 * 你需要将 nums 划分为 m 个 不相交的连续
 * 子数组
 * ，对于第 ith 个子数组 [li, ri]，子数组元素的按位 AND 运算结果等于 andValues[i]，
 * 换句话说，对所有的 1 <= i <= m，nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i] ，
 * 其中 & 表示按位 AND 运算符。
 *
 * 返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 -1
 */
public class MinimumValueSum {

    public static  int handle(int[] nums, int[] andValues) {
        return -1;
    }

    /**
     * 深度优先搜索
     */
    class Solution {
        private static final int INF = (1 << 20) - 1;
        private HashMap<Integer, Integer>[] memo;

        public int minimumValueSum(int[] nums, int[] andValues) {
            int n = nums.length, m = andValues.length;
            memo = new HashMap[m * n];
            for (int i = 0; i < m * n; ++i) {
                memo[i] = new HashMap<Integer, Integer>();
            }
            int res = dfs(0, 0, INF, nums, andValues);
            return res < INF ? res : -1;
        }

        private int dfs(int i, int j, int cur, int[] nums, int[] andValues) {
            int n = nums.length, m = andValues.length, key = i * m + j;
            if (i == nums.length && j == andValues.length) {
                return 0;
            }
            if (i == nums.length || j == andValues.length) {
                return INF;
            }
            if (memo[key].containsKey(cur)) {
                return memo[key].get(cur);
            }
            cur &= nums[i];
            if ((cur & andValues[j]) < andValues[j]) {
                return INF;
            }
            int res = dfs(i + 1, j, cur, nums, andValues);
            if (cur == andValues[j]) {
                res = Math.min(res, dfs(i + 1, j + 1, INF, nums, andValues) + nums[i]);
            }
            memo[key].put(cur, res);
            return res;
        }
    }

}
